package com.wu.leetcode.leetcode17;

import java.util.*;

/**
 * Leetcode17-电话号码的字母组合
 *
 * @author lynn
 * @date 2020/11/3 - 0:44
 */
public class Solution {

        public static List<String> letterCombinations(String digits) {
            List<String> res = new ArrayList<String>();
            if (digits.length() == 0) {
                return res;
            }
            Map<Character, String> map = new HashMap<>();
                map.put('2', "abc");
                map.put('3', "def");
                map.put('4', "ghi");
                map.put('5', "jkl");
                map.put('6', "mno");
                map.put('7', "pqrs");
                map.put('8', "tuv");
                map.put('9', "wxyz");
                //1.
            dfs(res, map, digits, 0, new StringBuffer());
            return res;
          //2.
          /*  Queue<String> queue = new LinkedList<>();
            queue.add("");
            for (int i = 0; i < digits.length(); i++) {
                String str = map.get(digits.charAt(i));
                int size = queue.size();
                for (int j = 0; j < size; j++) {
                    String s = queue.poll();
                    for (int k = 0; k < str.length(); k++) {
                        queue.add(s + str.charAt(k));
                    }
                }
            }
            return (List<String>) queue;*/
        }

        public static void dfs(List<String> res, Map<Character, String> map, String digits, int index, StringBuffer builder) {
            if (index == digits.length()) {
                res.add(builder.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = map.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    builder.append(letters.charAt(i));
                    dfs(res, map, digits, index + 1, builder);
                    builder.deleteCharAt(index);
                }
            }
        }

    public static void main(String[] args) {
        List<String> strings = letterCombinations("235");
        System.out.println(strings);
    }
}
